﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;

namespace ProjectEuler.Problems
{
    [EulerProblem(46, 5777)]
    [Description("What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?")]
    internal sealed class Problem046 : EulerProblem
    {
        public override Object Solve()
        {
            var sieve = new SieveOfEratosthenes(10000);

            return sieve
                .CompositesOdd()
                .First(c => !TwoSquares(c).Any(twsq => sieve.IsPrime(c - twsq)));
        }

        private static IEnumerable<Int32> TwoSquares(Int32 max)
        {
            var sqrtHalf = (Int32)(Math.Sqrt(max / 2));

            for (int i = sqrtHalf; i > 0; i--)
            {
                yield return 2 * (i * i);
            }
        }
    }
}
